package com.yt.ds.chapter2;

/**
 * @Author: lzf
 * @Date: 2020/7/15 10:55
 * @Description: 堆排序 ，原理是 先构造最大堆，然后将根节点(最大值)与最后一个节点对换，n--之后，再将对换后的节点下沉。
 */
public class HeapSort implements Sort {

    @Override
    public Comparable[] sort(Comparable[] array) {
        MaxPQ maxPQ = new MaxPQ<>(array);
        int n = maxPQ.getSize();
        for (int i = n / 2; i >= 1; i--) {
            maxPQ.sink(i, n);
        }
        while (n >= 1) {
            maxPQ.exch(1, n);
            n--;
            maxPQ.sink(1, n);
        }
        array = maxPQ.getPq();
        return array;
    }
}
